Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
Example 1:
Input: nums = [4,2,3] Output: true Explanation: You could modify the first4to1to get a non-decreasing array.
Example 2:
Input: nums = [4,2,1] Output: false Explanation: You can't get a non-decreasing array by modify at most one element.
Constraints:
n == nums.length1 <= n <= 104-105 <= nums[i] <= 105
Average Rating: 4.61 (18 votes)
Solution
Approach: Greedy
Intuition
The one thing that we should focus on here is the fact that the problem description says non-decreasing, which is just another way of saying increasing. In this case, it means the next element must always be greater than or equal to the current element. Thus, in an array, the item on the left must be less than or equal to the item on the right. Since we can only rectify a single violation of this rule, if more than one violation exists, it is impossible to make the array non-decreasing.
The first time we encounter such a violation i.e. nums[i - 1] > nums[i], we make a change. You don't actually have to make a change because the question doesn't ask us to give the final array in order, it just asks if it could become non-decreasing. Then, we move on with the rest of the array, and continue to check for other violations. If it ever so happens that the rule gets violated again, we return false since this would be the second violation of the rule. If we don't find a second violation, we can return true since rectifying the first violation made our array non-decreasing.
Whenever we encounter a violation at a particular index i, we need to check what modification we can make to make the array sorted. Let's see this scenario using an example.
Figure 1. A violation in the sorted array.
In the example above, we consider the numbers 4, 5, 3 for deciding on how to fix the violation or. In this case, the correct modification is to change the number 3 to 5. If we change 5 to 3, then we won't be fixing the violation because the resulting array would be 3, 4, 3, 3, 6, 8.
Figure 2. Rectifying a single violation leading to sorted array.
The basic decision making process for fixing a violation is listed below. Without considering the number at the index i - 2, we won't be able to choose between updating nums[i] or nums[i - 1]. The modification has to fit in with the sorted nature of the array.
if nums[i - 2] > nums[i] then
nums[i] = nums[i - 1]
else
nums[i - 1] = nums[i]
Once we make the modification, we expect that the rest of the array will be sorted. If that is not the case, then we return false from our function. Some arrays will have violations in different places e.g. a 10 element array where nums[4] > nums[5] and also nums[8] > nums[9]. This array cannot be sorted by only fixing the violation at nums[5].
Additionally, it is possible that a modification in the array leads to another violation that did not exist before. Let's consider an example where this can happen.
Figure 3. Rectifying a single violation introduces a new violation.
Algorithm
- We iterate over the array until we reach the end of the array or find a violation.
- If we reach the end of the array, we know it is sorted and we return
true. - Otherwise, we found a violation. We consider the
nums[i - 2]to fix the violation.- If the violation is at the index
1, we won't have anums[i - 2]available. In that case we simply setnums[i - 1]equal tonums[i]. - Otherwise, we check if
nums[i - 2] <= nums[i]in which case we setnums[i - 1]equal tonums[i]. - Finaly, if
nums[i - 2] > nums[i], then we setnums[i]equal tonums[i - 1].
- If the violation is at the index
- Once we make the modification, we simply iterate over the remaining array. If we find another violation, we return
false. Otherwise, we returntrueonce the iteration is complete.
Implementation
Complexity Analysis
-
Time Complexity: O(n) considering there are n elements in the array and we process each element at most once.
-
Space Complexity: O(1) since we don't use any additional space apart from a couple of variables for executing this algorithm.
May 4, 2021 2:54 PM
Why modify the input array? Yes, is a peeve of mine :) We are not adding value, i.e. sorting, so this code is destructive. Passing in the same array twice could yield different results (i.e. non-deterministic).
Instead, try something like this:
public bool CheckPossibility(int[] nums) {
int badIdx = -1;
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (badIdx == -1) {
badIdx = i;
}
else {
return false;
}
}
}
if (badIdx <= 0 || badIdx == nums.Length - 2) {
return true;
}
else {
return nums[badIdx - 1] <= nums[badIdx + 1] || nums[badIdx] <= nums[badIdx + 2];
}
}
April 18, 2021 3:11 AM
Hi, dudes! How's tricks?
class Solution {
func checkPossibility(_ nums: [Int]) -> Bool {
guard nums.count > 2 else { return true }
var modify = 0, n = nums.count - 1
while n != 0 {
if nums[n] < nums[n-1] {
modify += 1
if n > 1,
n < nums.count - 1,
nums[n+1] < nums[n-1],
nums[n-2] > nums[n] { return false }
}
if modify > 1 { return false }
n -= 1
}
return true
}
}
import XCTest
// Executed 2 tests, with 0 failures (0 unexpected) in 0.004 (0.006) seconds
class Tests: XCTestCase {
private let s = Solution()
func testExample1() {
XCTAssertTrue(s.checkPossibility([4,2,3])) // success
}
func testExample2() {
XCTAssertFalse(s.checkPossibility([4,2,1])) // success
}
}
Tests.defaultTestSuite.run()
April 1, 2021 3:20 PM
This solution is simple and easy to understand with visualized diagrams. Just one more thing to consider is that it's always better solution not to modify input.
here is my solution not to modify input. It just checks whether it's possible to make local non decreasing state and then if it is not possible, just return false.
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int len = nums.size();
bool modified = false;
for (int i=0; i < len-1; i++) {
if (nums[i] > nums[i+1]) {
if (modified) {
return false;
}
if (i-1 < 0 || nums[i-1] <= nums[i+1]) {
// in this case, you can change nums[i] = x (nums[i-1] <= x <= nums[i+1])
} else if (i + 2 >= len || nums[i] <= nums[i+2]) {
// in this case, you can change nums[i+1] = x (nums[i] <= x <= nums[i+2])
} else {
// if it's not the both of them, it's not possible to make sorted state with one modification
return false;
}
modified = true;
}
}
return true;
}
};
May 4, 2021 1:40 PM
Follow up: what if you can change at most k elements?
Another way to look at this is this, if the longest increasing subsequence is greater than equal to n-1, then return true, else return false, O(nlogn) though, just hit me hence tried, passing all test cases, though obviously the solution approach is better.
May 17, 2021 5:01 AM
Wow, this question was trickier than i thought at the beginning.
This is medium? I have been staring into space with this problem :(
How would you rate this? Pop the bad one and see if it's sorted.
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
if all(nums[i] <= nums[i+1] for i in range(len(nums)-1)):
return True
for i in range(0,len(nums)):
o = list(nums)
o.pop(i)
if all(o[x] <= o[x+1] for x in range(len(o)-1)):
return True
return False
Last Edit: May 6, 2021 5:55 AM
We can insert a minimum value to remove i < 2 check in if i < 2 or nums[i - 2] <= nums[i]:, here is the code in Python3,
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
nums.insert(0, -10**5)
hit = False
for i in range(2, len(nums)):
if nums[i-1] > nums[i]:
if hit:
return False
hit = True
if nums[i-2] > nums[i]:
nums[i] = nums[i-1]
else:
nums[i-1] = nums[i-2]
return True
Here is a straightforward approach O(n) using stack.
bool checkPossibility(vector<int>& nums) {
stack<int> stk;
bool modified=false;
stk.push(INT_MIN); // if any changes at num[0] are required
stk.push(nums[0]);
for (int i=1; i<nums.size(); i++){
if (nums[i]>=nums[i-1]){
stk.push(nums[i]);
}
else{
if (modified) return false;// already modified a value?
modified=true;
//either (a) make num[i] to be equal to nums[i-1]
//or (b) make the num[i-1] to be the least possible value possible for it
// we could only do one of the above to make the array right
int last=stk.top();
stk.pop();
int largestOnStack=stk.top();
if (largestOnStack>nums[i]){nums[i]= last;} // [... 4, 5, 3, ...] we will have to modify 3 to 5
else
last= largestOnStack; // [...3, 5, 4...] we can change 5 to 4 and the array would still be valid!
stk.push(last);
stk.push(nums[i]);
}
}
return true;
}Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/04/2021 19:09 | Accepted | 32 ms | 27 MB | cpp |
| 05/04/2021 19:04 | Wrong Answer | N/A | N/A | cpp |
| 06/27/2020 14:33 | Accepted | 216 ms | 15 MB | python3 |
| 06/27/2020 14:24 | Wrong Answer | N/A | N/A | cpp |
| 06/27/2020 14:23 | Wrong Answer | N/A | N/A | cpp |
xxxxxxxxxxclass Solution {public: bool checkPossibility(vector<int>& nums) { }};


